/* 

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

 

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
示例 3：

输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000
示例 4：

输入：nums1 = [], nums2 = [1]
输出：1.00000
示例 5：

输入：nums1 = [2], nums2 = []
输出：2.00000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

*/

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */

/* 和官方题解视频配合解答 */
var findMedianSortedArrays = function (nums1, nums2) {
    if (nums1.length > nums2.length) {
        [nums1, nums2] = [nums2, nums1];
    }

    const m = nums1.length;
    const n = nums2.length;

    // 分割线左边的所有元素需要满足的个数 m + (n - m + 1) / 2;
    const totalLeft = Math.floor((m + n + 1) / 2);

    // 在 nums1 的区间 [0, m] 里查找恰当的分割线，
    // 使得 nums1[i - 1] <= nums2[j] && nums2[j - 1] <= nums1[i]
    let left = 0;
    let right = m;

    while (left < right) {
        const i = Math.floor(left + (right - left + 1) / 2);
        const j = totalLeft - i;
        if (nums1[i - 1] > nums2[j]) {
            // 下一轮搜索的区间 [left, i - 1]
            right = i - 1;
        } else {
            // 下一轮搜索的区间 [i, right]
            left = i;
        }
    }

    const i = left,
        j = totalLeft - i;
    const nums1LeftMax = i === 0 ? -Infinity : nums1[i - 1],
        nums1RightMin = i === m ? Infinity : nums1[i],
        nums2LeftMax = j === 0 ? -Infinity : nums2[j - 1],
        nums2RightMin = j === n ? Infinity : nums2[j];

    if (((m + n) % 2) === 1) {
        return Math.max(nums1LeftMax, nums2LeftMax);
    } else {
        return ((Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin))) / 2;
    }
};